"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
    def __init__(self):
        self.visited = {}

    def cloneGraph(self, node):
        return self.dfs(node)

    def dfs(self, node):
        if node is None:
            return None
        if node in self.visited:
            return self.visited[node]

        newNode = Node(node.val)
        self.visited[node] = newNode

        for neighbor in node.neighbors:
            newNode.neighbors.append(self.dfs(neighbor))
        return newNode
